//给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
//
//
//
// 示例 1：
//
//
//输入：n = 3
//输出：5
//
//
// 示例 2：
//
//
//输入：n = 1
//输出：1
//
//
//
//
// 提示：
//
//
// 1 <= n <= 19
//
//
// Related Topics 树 二叉搜索树 数学 动态规划 二叉树 👍 2188 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
function numTrees(n: number): number {
    /*
    dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量

    元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量

    元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量

    元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

    有2个元素的搜索树数量就是dp[2]。

    有1个元素的搜索树数量就是dp[1]。

    有0个元素的搜索树数量就是dp[0]。

    所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
     */
    /**
     dp[i]: i个节点对应的种树
     dp[0]: -1; 无意义；
     dp[1]: 1;
     ...
     dp[i]: 2 * dp[i - 1] +
     (dp[1] * dp[i - 2] + dp[2] * dp[i - 3] + ... + dp[i - 2] * dp[1]); 从1加到i-2
     */
    const dp: number[] = [];
    dp[0] = -1; // 表示无意义
    dp[1] = 1
    for (let i = 2; i <= n; i++) {
        // 当前节点作为头结点和最小节点作为根节点的情况
        dp[i] = 2 * dp[i - 1];
        // 遍历除当前节点和最小节点的每个节点当头结点 统计数量
        for (let j = 1, end = i - 1; j < end; j++) {
            dp[i] += dp[j] * dp[end - j];
        }
    }
    return dp[n];
};
//leetcode submit region end(Prohibit modification and deletion)
